class Solution {
public://前缀和 + 二分
    vector<int> sum; //前缀和数组
    int lower_bound(int begin,int end,int target){
        if (sum[end]<target) return -1;//最大值比target小;否则一定可以找到
        //找到符合条件的最小index
        while(begin<end){
            int mid = begin + (end - begin) / 2;
            if (sum[mid]>=target){
                end = mid;
            }else{
                begin = mid + 1;
            }
        }
        return begin;
    }

    int minSubArrayLen(int target, vector<int>& nums) {
        if (nums.size()==0) return 0;
        //本题可用二分，因为元素为正，前缀和永远是递增的
        //sum[i,j] = sum[j] - sum[i-1] 用前缀和求区间的和值
       
        int m =0;
        sum.push_back(0); //前缀和从[1,n]  这样便于二分的target判断 begin-1要考虑begin为0的特殊情况
        for(int i=0;i<nums.size();i++){
            m+=nums[i];
            sum.push_back(m);
        }
        //对每个数组位置枚举结果位置j，如果合法(>=target)，就更新结果位置，搜索更短的结果
        int minLen = nums.size()+1; //取一个不可能的最大值(最大为nums.size())
        for(int i=1;i<=nums.size();i++){//搜sum数组
            int judgebound = target + sum[i-1];//这是补上前面的和，直接在sum中搜[1,nums.size()]比这个值大的最小位置  而非[i,nums.size()] 因为已经加上sum[i-1]了
            //int end = lower_bound(i,nums.size()-1,judgebound);
            int end = lower_bound(1,nums.size(),judgebound);
            if (end!=-1){
                minLen = minLen<(end-i + 1)?minLen:(end-i + 1);
            }
        }
        return (minLen==nums.size()+1)?0:minLen;

    }
};